package ustc.xiaoyang.karl.simulation;

import java.util.Arrays;

/**
 * LCR 146 螺旋遍历二维数组
 * 标记法
 */
public class SpiralTraverseArray146LCR {
    public static void main(String[] args) {

        System.out.println(Arrays.toString(new SpiralTraverseArray146LCR().spiralArray(new int[][]{{1,2,3},{4,5,6},{7,8,9}})));
    }
    private static final int[][] DIR = {{0,1},{1,0},{0,-1},{-1,0}};
    public int[] spiralArray(int[][] array){
        if(array == null || array.length == 0) return new int[0];
        int m = array.length;
        int n = array[0].length;
        int[] ans = new int[m*n];
        int i = 0;
        int j = 0;
        int dir = 0;
        for(int k = 0; k<m*n ; k++){
            ans[k] = array[i][j];
            array[i][j] = Integer.MAX_VALUE;
            int x = i + DIR[dir][0];
            int y = j + DIR[dir][1];
            if(x < 0 || x >= m || y < 0 || y >= n || array[x][y] == Integer.MAX_VALUE){
                dir = (dir + 1) % 4;
            }
            i = i + DIR[dir][0];
            j = j + DIR[dir][1];
        }
        return ans;
    }
}